// 我们将乱序的红白蓝三色小球排列成有序的红白蓝三色的同颜色在一起的小球组。
// 要用三个指针，一前begin，一中current，一后end，俩俩交换。
// 1、current遍历，整个数组序列，current指1不动，
// 2、current指0，与begin交换，而后current++，begin++，
// 3、current指2，与end交换，而后，current不动，end--。
//    (万一end之前指的是0，而current交换之后，current此刻指的是0了，此时，current不能动啊，指的是0，还得与begin交换列。)

function partionColorSort(arr) {
    const length = arr.length;
    let currentIndex = 0;
    let beginIndex = 0;
    let endIndex = length - 1;
    while (currentIndex < endIndex) {
        if (arr[currentIndex] == 0) {
            swap(arr, currentIndex, beginIndex);
            beginIndex++;
            currentIndex++;
        } else if (arr[currentIndex] == 2) {
            swap(arr, currentIndex, endIndex);
            endIndex--;
        } else {
            currentIndex++;
        }
    }
    return arr;
}

function swap(arr, i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

let data = [0, 1, 2, 1, 1, 2, 0, 2, 1, 0];
let res = partionColorSort(data);
console.log(res);